package com.leetcode.sort;


/**
 * 对链表进行插入排序
 */
public class Solution147 {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val; this.next = next;
        }
    }

    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode newHead = new ListNode();
        ListNode point = newHead;

        while (head != null) {
            while (point.next != null) {
                if (head.val < point.next.val) {
                    ListNode node = new ListNode(head.val);
                    node.next = point.next;
                    point.next = node;
                    break;
                }
                point = point.next;
            }
            if (point.next == null) {
                ListNode node = new ListNode(head.val);
                point.next = node;
            }
            head = head.next;
            point = newHead;
        }

        return newHead.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(2);
        node1.next = node2;
        ListNode node3 = new ListNode(1);
        node2.next = node3;
        ListNode node4 = new ListNode(3);
        node3.next = node4;

        Solution147 solution147 = new Solution147();
        System.out.println(solution147.insertionSortList(node1).toString());
    }
}
